/**
 * @a https://leetcode.cn/problems/permutation-sequence/
 */

#include "../common.h"

class Solution {
public:
    string getPermutation(int n, int k) {
        // 数学方法
        vector<int> factorial(n);
        factorial[0] = 1;
        for(int i = 1; i < n; ++i){
            factorial[i] = factorial[i - 1] * i;
        }
        string ret;
        vector<int> nr(n);
        for(int i = 1; i <= n; ++i){
            nr[i - 1] = i;
        }
        k--;
        for(int i = n - 1; i >= 0; --i){
            int pos = k / factorial[i];
            ret.push_back(nr[pos]+'0');
            for(int j = pos; j < i; j++){
                nr[j] = nr[j + 1];
            }
            k %= factorial[i];
        }
        return ret;
    }
};
